4004. Is there a cycle?

 

A directed graph is given. Determine whether it contains a cycle.

 

Input. The first line contains a single integer – the number of vertices n (n ≤ 50).

Then follow n lines, each containing n integers – the adjacency matrix of the graph. Each number is either 0 or 1. The j-th number in the i-th line is equal to 1 if and only if there is an edge from vertex i to vertex j.

It is guaranteed that the main diagonal of the matrix contains only zeros.

 

Output. Print 0 if the graph contains no cycles, and 1 if there is at least one cycle.

 

Sample input 1

Sample output 1

3

0 1 1

0 0 1

0 0 0

0

 

 

Sample input 2

Sample output 2

5

0 1 1 0 0

0 0 0 0 0

0 1 0 1 0

0 0 0 0 1

1 0 0 0 0

1

 

 

SOLUTION

depth first search

 

Algorithm analysis

Perform a depth-first search on the directed graph, treating it as disconnected. To do this, use an array used to track the color of each vertex:

·        used[v] = 0 – vertex v is white, meaning it has not been visited yet;

·        used[v] = 1 – vertex v is gray, meaning it has been entered but its sons have not yet been fully processed;

·        used[v] = 2 – vertex v is black, meaning both it and all its sons have been fully processed.

A cycle exists in a directed graph if, during depth-first search, we find an edge leading to a gray vertex.

 

Example

The graphs given in the problem statement have the following structure:

 

Algorithm implementation

Declare the adjacency matrix g and the array used to store the states of the vertices.

 

#define MAX 51

int g[MAX][MAX], used[MAX];

 

The function dfs performs a depth-first traversal of the graph, starting from vertex v.

 

void dfs(int v)

{

 

Mark vertex v as gray to indicate that we have entered it.

 

  used[v] = 1;

 

Iterate over all vertices that can be reached from vertex v.

 

  for (int i = 1; i <= n; i++)

 

There is an edge from vertex v to vertex i if g[v][i] = 1.

 

    if (g[v][i])

    {

 

If vertex i is gray, then during the depth-first search we have encountered a gray vertex – a cycle is found.

 

      if (used[i] == 1) flag = 1;

 

If vertex i is white, it means it has not been visited yet. Continue the depth-first search from it.

 

      else if (used[i] == 0) dfs(i);

 

If vertex i is black, do nothing.

 

    }

 

After processing all sons of vertex v, mark it as black.

 

  used[v] = 2;

}

 

The main part of the program. Read the adjacency matrix.

 

scanf("%d", &n);

for (i = 1; i <= n; i++)

for (j = 1; j <= n; j++)

  scanf("%d", &g[i][j]);

 

Perform a depth-first search on the directed graph (as disconnected).

 

flag = 0;

for (i = 1; i <= n; i++)

  if (used[i] == 0) dfs(i);

 

Print the answer.

 

printf("%d\n", flag);

 

Java implementation

 

import java.util.*;

 

public class Main

{

  static int g[][], used[];

  static int n, flag;

  static void dfs(int v)

  {

    // mark vertex v as GRAY, make an entrance to v

    used[v] = 1;

 

    // we try to go from v to i, i = 1,2,...,n

    for (int i = 1; i <= n; i++)

      // if there exists an edge from v to i

      if (g[v][i] == 1)

      {

         // if vertex i is GRAY, we meet cycle

         if (used[i] == 1) flag = 1;

         // if vertex i is not visited, run dfs from there

         else if (used[i] == 0) dfs(i);

        // if vertex i is black (used[i] = 2), do nothing

      }

    // mark vertex v as BLACK, make an exit from v

    used[v] = 2;

  }

 

  public static void main(String[] args)

  {

    Scanner con = new Scanner(System.in);

    n = con.nextInt();

    g = new int[n+1][n+1];

    used = new int[n+1];

 

    for(int i = 1; i <= n; i++)

    for(int j = 1; j <= n; j++)

      g[i][j] = con.nextInt();

 

    flag = 0;

    // run dfs on directed graph like on disconnected graph

    for (int i = 1; i <= n; i++)

      if (used[i] == 0) dfs(i);

 

    System.out.println(flag);   

  }

}